import java.util.Arrays;

public class TestHeap {
    public int[] elem;
    public int usedSize;
    public TestHeap(){
        this.elem=new int[10];
    }
    public void initElem(int[] array){
        for(int i=0;i<array.length;i++){
            this.elem[i]=array[i];
            usedSize++;
        }
    }
    public void createHeap(){
        for(int parent=(usedSize-1-1)/2;parent>=0;parent--){
            shftDown(parent,usedSize);
        }
    }

    private void shftDown(int parent, int usedSize) {
        //找到父节点的左节点,即child
        int child=parent*2+1;
        while(child<usedSize) {
            //child<usedSize是为了看该父节点的左节点是否存在
            //比较左右孩子的最大值
            if (child+1 < usedSize && elem[child] < elem[child + 1]) {
                child++;
            }
            //到这child一定是左右孩子的最大值节点的下标
            if (elem[child] > elem[parent]) {
                swap(elem, parent, child);
                parent = child;
                child = parent * 2 + 1;
            }else{
                //既然是线下调整，那么到这里就已经是调整完毕了
                break;
            }
        }
    }
    private void swap(int[] elem, int parent, int child) {
        int tmp=elem[parent];
        elem[parent]=elem[child];
        elem[child]=tmp;

    }
    public void offer(int val){
        if(isFull()){
            //注意要elem接收啊
           elem= Arrays.copyOf(elem,elem.length*2);
        }
        elem[usedSize]=val;
        shftUp(usedSize);
        usedSize++;

    }
    //向上调整
    public void shftUp(int child){
        int parent=(child-1)/2;
        while(parent>=0){
            if(elem[child]>elem[parent]){
                swap(elem,parent,child);
                child=parent;
                parent=(child-1)/2;
            }else{
                break;
            }
        }
    }

    public boolean isFull(){
        return usedSize== elem.length;
    }
    public void poll(){
        if(isEmpty()){
            return;
        }
        swap(elem,0,usedSize-1);
        usedSize--;
        shftDown(0,usedSize);

    }
    public boolean isEmpty(){
        return usedSize==0;
    }

    //堆排序(从小到大)
    //注意该堆是大根堆才能排序
    public void heapSort(){
        int end=usedSize-1;
        while(end>0){
            swap(elem,0,end);
            //shftDown的参数end,是元素的个数,这里传入为end是已经少了一个了
            shftDown(0,end);
            end--;
        }
    }

    @Override
    public String toString() {
        return "TestHeap{" +
                "elem=" + Arrays.toString(elem) +
                ", usedSize=" + usedSize +
                '}';
    }
}


